﻿#region

using Common.Utilities;

#endregion

namespace AdvancedTraining.Lesson37;

/// <summary>
/// LeetCode 0406: 根据身高重建队列
/// </summary>
/// <remarks>
/// 假设有打乱顺序的一群人站成一个队列，数组 people 表示每个人的属性。
/// people[i] = [heighti, ki] 表示第 i 个人的身高为 heighti，前面正好有 ki 个身高大于或等于 heighti 的人。
/// 请你重新构造并返回输入数组 people 所表示的队列。
/// 返回的队列应该格式化为数组 queue，其中 queue[j] = [heightj, kj] 是队列中第 j 个人的属性。
///
/// 算法思路：
/// 1. 将 people 按照身高从高到矮排序，如果身高相同，则按照 k 从小到大排序
/// 2. 依次将每个人插入到队列的第 k 个位置
///
/// 方法一：使用 ArrayList 插入，时间复杂度 O(N²)
/// 方法二：使用 SBTree（Size Balanced Tree）插入，时间复杂度 O(N logN)
///
/// 时间复杂度：
/// - 方法一：O(N²)，因为每次插入需要移动元素
/// - 方法二：O(N logN)，因为SBTree的插入和查询都是O(logN)
///
/// 空间复杂度：O(N)，用于存储队列
/// </remarks>
public class QueueReconstructionByHeight //leetcode_0406
{
    /// <summary>
    /// 方法一：使用ArrayList重建队列
    /// </summary>
    /// <param name="people">输入的人群数组</param>
    /// <returns>重建后的队列</returns>
    public static int[,] reconstructQueue1(int[,] people)
    {
        // 修复：使用GetLength(0)获取二维数组的行数，而不是使用Length
        var N = people.GetLength(0);
        var units = new Unit[N];
        for (var i = 0; i < N; i++) units[i] = new Unit(people[i, 0], people[i, 1]);

        Array.Sort(units, new UnitComparator());
        var arrList = new List<Unit>();
        foreach (var unit in units) arrList.Insert(unit.k, unit);
        var ans = new int[N, 2];
        var index = 0;
        foreach (var unit in arrList)
        {
            ans[index, 0] = unit.h;
            ans[index++, 1] = unit.k;
        }

        return ans;
    }

    /// <summary>
    /// 方法二：使用SBTree重建队列
    /// </summary>
    /// <param name="people">输入的人群数组</param>
    /// <returns>重建后的队列</returns>
    public static int[,] reconstructQueue2(int[,] people)
    {
        // 修复：使用GetLength(0)获取二维数组的行数，而不是使用Length
        var N = people.GetLength(0);
        var units = new Unit[N];
        for (var i = 0; i < N; i++) units[i] = new Unit(people[i, 0], people[i, 1]);

        Array.Sort(units, new UnitComparator());
        var tree = new SBTree();
        for (var i = 0; i < N; i++) tree.Insert(units[i].k, i);

        var allIndexes = tree.allIndexes();
        var ans = new int[N, 2];
        var index = 0;
        foreach (var arri in allIndexes)
        {
            ans[index, 0] = units[arri].h;
            ans[index++, 1] = units[arri].k;
        }

        return ans;
    }

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== QueueReconstructionByHeight 测试 ===");

        // 测试用例1：LeetCode官方示例
        var people1 = new int[,] { { 7, 0 }, { 4, 4 }, { 7, 1 }, { 5, 0 }, { 6, 1 }, { 5, 2 } };
        var result1 = reconstructQueue1(people1);
        Console.WriteLine("测试1 - 官方示例(方法一):");
        PrintMatrix(result1);

        var result1_2 = reconstructQueue2(people1);
        Console.WriteLine("测试1 - 官方示例(方法二):");
        PrintMatrix(result1_2);

        // 测试用例2：简单情况
        var people2 = new int[,] { { 6, 0 }, { 5, 0 }, { 4, 0 }, { 3, 2 }, { 2, 2 }, { 1, 4 } };
        var result2 = reconstructQueue1(people2);
        Console.WriteLine("测试2 - 简单情况:");
        PrintMatrix(result2);

        // 测试用例3：所有人身高相同
        var people3 = new int[,] { { 5, 0 }, { 5, 1 }, { 5, 2 } };
        var result3 = reconstructQueue1(people3);
        Console.WriteLine("测试3 - 身高相同:");
        PrintMatrix(result3);

        // 测试用例4：k值递增
        var people4 = new int[,] { { 5, 0 }, { 4, 1 }, { 3, 2 }, { 2, 3 } };
        var result4 = reconstructQueue1(people4);
        Console.WriteLine("测试4 - k值递增:");
        PrintMatrix(result4);

        // 测试用例5：单个元素
        var people5 = new int[,] { { 5, 0 } };
        var result5 = reconstructQueue1(people5);
        Console.WriteLine("测试5 - 单个元素:");
        PrintMatrix(result5);

        Console.WriteLine("=== 性能对比测试 ===");
        PerformanceTest();

        Console.WriteLine("=== 测试完成 ===");
    }

    /// <summary>
    /// 打印二维矩阵
    /// </summary>
    private static void PrintMatrix(int[,] matrix)
    {
        Console.Write("[");
        for (var i = 0; i < matrix.GetLength(0); i++)
        {
            Console.Write($"[{matrix[i, 0]},{matrix[i, 1]}]");
            if (i < matrix.GetLength(0) - 1) Console.Write(", ");
        }
        Console.WriteLine("]");
    }

    /// <summary>
    /// 性能对比测试
    /// </summary>
    private static void PerformanceTest()
    {
        const int test = 10000;
        const int max = 1000000;

        Console.WriteLine("开始性能对比测试...");
        Console.WriteLine("测试数据量: " + test);

        // 生成测试数据
        var random = new Random();
        var people = new int[test, 2];
        for (var i = 0; i < test; i++)
        {
            people[i, 0] = random.Next(1, 100);
            people[i, 1] = random.Next(0, Math.Min(i, 50));
        }

        // 测试方法一
        var stopwatch = System.Diagnostics.Stopwatch.StartNew();
        var result1 = reconstructQueue1(people);
        stopwatch.Stop();
        Console.WriteLine("方法一(ArrayList)执行时间: " + stopwatch.ElapsedMilliseconds + "ms");

        // 测试方法二
        stopwatch.Restart();
        var result2 = reconstructQueue2(people);
        stopwatch.Stop();
        Console.WriteLine("方法二(SBTree)执行时间: " + stopwatch.ElapsedMilliseconds + "ms");

        // 验证两种方法结果是否一致
        var equal = true;
        if (result1.GetLength(0) == result2.GetLength(0))
        {
            for (var i = 0; i < result1.GetLength(0); i++)
            {
                if (result1[i, 0] != result2[i, 0] || result1[i, 1] != result2[i, 1])
                {
                    equal = false;
                    break;
                }
            }
        }
        else
        {
            equal = false;
        }

        Console.WriteLine("两种方法结果一致性: " + (equal ? "通过" : "失败"));
    }

    /// <summary>
    /// 表示一个人的单位，包含身高和前面大于等于身高的人数
    /// </summary>
    public class Unit
    {
        /// <summary>
        /// 身高
        /// </summary>
        public int h;

        /// <summary>
        /// 前面大于等于身高的人数
        /// </summary>
        public int k;

        /// <summary>
        /// 构造函数
        /// </summary>
        /// <param name="height">身高</param>
        /// <param name="greater">前面大于等于身高的人数</param>
        public Unit(int height, int greater)
        {
            h = height;
            k = greater;
        }
    }

    /// <summary>
    /// Unit比较器，用于排序
    /// </summary>
    public class UnitComparator : IComparer<Unit>
    {
        /// <summary>
        /// 比较两个Unit
        /// </summary>
        /// <param name="o1">第一个Unit</param>
        /// <param name="o2">第二个Unit</param>
        /// <returns>比较结果</returns>
        public virtual int Compare(Unit o1, Unit o2)
        {
            // 身高降序，k升序
            return o1.h != o2.h ? o2.h - o1.h : o1.k - o2.k;
        }
    }

    /// <summary>
    /// Size Balanced Tree（大小平衡树）节点
    /// </summary>
    public class SBTNode
    {
        /// <summary>
        /// 左子节点
        /// </summary>
        public SBTNode l;

        /// <summary>
        /// 右子节点
        /// </summary>
        public SBTNode r;

        /// <summary>
        /// 子树大小
        /// </summary>
        public int size;

        /// <summary>
        /// 节点值（索引）
        /// </summary>
        public int value;

        /// <summary>
        /// 构造函数
        /// </summary>
        /// <param name="arrIndex">数组索引</param>
        public SBTNode(int arrIndex)
        {
            value = arrIndex;
            size = 1;
        }
    }

    /// <summary>
    /// Size Balanced Tree（大小平衡树）
    /// 支持O(logN)时间的插入、删除和查找操作
    /// </summary>
    public class SBTree
    {
        /// <summary>
        /// 根节点
        /// </summary>
        internal SBTNode root;

        internal virtual SBTNode RightRotate(SBTNode cur)
        {
            var leftNode = cur.l;
            cur.l = leftNode.r;
            leftNode.r = cur;
            leftNode.size = cur.size;
            cur.size = (cur.l != null ? cur.l.size : 0) + (cur.r != null ? cur.r.size : 0) + 1;
            return leftNode;
        }

        internal virtual SBTNode LeftRotate(SBTNode cur)
        {
            var rightNode = cur.r;
            cur.r = rightNode.l;
            rightNode.l = cur;
            rightNode.size = cur.size;
            cur.size = (cur.l != null ? cur.l.size : 0) + (cur.r != null ? cur.r.size : 0) + 1;
            return rightNode;
        }

        internal virtual SBTNode Maintain(SBTNode cur)
        {
            if (cur == null) return null;

            var leftSize = cur.l != null ? cur.l.size : 0;
            var leftLeftSize = cur.l != null && cur.l.l != null ? cur.l.l.size : 0;
            var leftRightSize = cur.l != null && cur.l.r != null ? cur.l.r.size : 0;
            var rightSize = cur.r != null ? cur.r.size : 0;
            var rightLeftSize = cur.r != null && cur.r.l != null ? cur.r.l.size : 0;
            var rightRightSize = cur.r != null && cur.r.r != null ? cur.r.r.size : 0;
            if (leftLeftSize > rightSize)
            {
                cur = RightRotate(cur);
                cur.r = Maintain(cur.r);
                cur = Maintain(cur);
            }
            else if (leftRightSize > rightSize)
            {
                cur.l = LeftRotate(cur.l);
                cur = RightRotate(cur);
                cur.l = Maintain(cur.l);
                cur.r = Maintain(cur.r);
                cur = Maintain(cur);
            }
            else if (rightRightSize > leftSize)
            {
                cur = LeftRotate(cur);
                cur.l = Maintain(cur.l);
                cur = Maintain(cur);
            }
            else if (rightLeftSize > leftSize)
            {
                cur.r = RightRotate(cur.r);
                cur = LeftRotate(cur);
                cur.l = Maintain(cur.l);
                cur.r = Maintain(cur.r);
                cur = Maintain(cur);
            }

            return cur;
        }

        internal virtual SBTNode Insert(SBTNode root, int index, SBTNode cur)
        {
            if (root == null) return cur;

            root.size++;
            var leftAndHeadSize = (root.l != null ? root.l.size : 0) + 1;
            if (index < leftAndHeadSize)
                root.l = Insert(root.l, index, cur);
            else
                root.r = Insert(root.r, index - leftAndHeadSize, cur);

            root = Maintain(root);
            return root;
        }

        internal virtual SBTNode Get(SBTNode root, int index)
        {
            var leftSize = root.l != null ? root.l.size : 0;
            if (index < leftSize)
                return Get(root.l, index);
            if (index == leftSize)
                return root;
            return Get(root.r, index - leftSize - 1);
        }

        internal virtual void Process(SBTNode head, LinkedList<int> indexes)
        {
            if (head == null) return;

            Process(head.l, indexes);
            indexes.AddLast(head.value);
            Process(head.r, indexes);
        }

        /// <summary>
        /// 在指定位置插入节点
        /// </summary>
        /// <param name="index">插入位置</param>
        /// <param name="value">节点值</param>
        public virtual void Insert(int index, int value)
        {
            var cur = new SBTNode(value);
            if (root == null)
            {
                root = cur;
            }
            else
            {
                if (index <= root.size) root = Insert(root, index, cur);
            }
        }

        /// <summary>
        /// 获取指定位置的节点值
        /// </summary>
        /// <param name="index">位置索引</param>
        /// <returns>节点值</returns>
        public virtual int Get(int index)
        {
            var ans = Get(root, index);
            return ans.value;
        }

        /// <summary>
        /// 获取所有索引（中序遍历）
        /// </summary>
        /// <returns>所有索引的链表</returns>
        public virtual LinkedList<int> allIndexes()
        {
            var indexes = new LinkedList<int>();
            Process(root, indexes);
            return indexes;
        }
    }
}